package _02_greedy_algorithm.coinchange;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author: mornd
 * @dateTime: 2023/7/19 - 14:38
 * 零钱兑换
 */
public class Leetcode518 {

    /**
     * leetcode 518
     * 数组 coins 表示不同面额的硬币，amount 表示总金额
     * 计算可以凑成总金额的硬币组合数，无法凑出返回0
     * 假设每一种面额的硬币有无限个
     */
    @Test
    public void test1() {
//        int change = coinChange(0, new int[]{1, 2, 5}, 5, new LinkedList<>(), true);
//        int change = coinChange(0, new int[]{5,2,1}, 5, new LinkedList<>(), true);
//        int change = coinChange(0, new int[]{25, 10, 5, 1}, 41, new LinkedList<>(), true);
        Integer[] coins = {25, 10, 1, 5};
        Arrays.sort(coins);
        int change = coinChange(coins.length - 1, coins, 41, new LinkedList<>(), true);
        System.out.println(change);
    }

    private int coinChange(int index, Integer[] coins, int amount, LinkedList<Integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[index]);
        }

        int count = 0;

        if (amount < 0) {
            print("×", stack);
            // 无解
        } else if (amount == 0) {
            print("√", stack);
            // 有解
            count = 1;
        } else {
            // 继续递归
            for (int i = index; i >= 0; i--) {
                count += coinChange(i, coins, amount - coins[i], stack, false);
            }
        }

        if (!stack.isEmpty()) {
            stack.pop();
        }
        return count;
    }

    private void print(String flag, LinkedList<Integer> stack) {
        if (stack.isEmpty()) {
            System.out.println("[]");
            return;
        }
        System.out.print("[");
        for (int i = stack.size() - 1; i >= 0; i--) {
            System.out.print(stack.get(i));
            if (i != 0) {
                System.out.print(", ");
            } else {
                System.out.print("]");
            }
        }
        System.out.println("\t" + flag);
    }

}
